Search Results

Logarithmic space bounded complexity classes such as L and NL play a central role in space bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space bounded computation was developed only in the last decade by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). They defined the operators para_W and para_β for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators para_W and para_β by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, para_{W[1]} and para_{βtail}. Then, we consider counting versions of all four operators applied to logspace and obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0,1)-matrices is #para_{βtail} L-hard and can be written as the difference of two functions in #para_{βtail} L. These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of these classes. For example, we show that the closure of #para_{βtail} L under parameterised logspace parsimonious reductions coincides with #para_β L, that is, modulo parameterised reductions, tail-nondeterminism with read-once access is the same as read-once nondeterminism. Initiating the study of closure properties of these parameterised logspace counting classes, we show that all introduced classes are closed under addition and multiplication, and those without tail-nondeterminism are closed under parameterised logspace parsimonious reductions. Also, we show that the counting classes defined can naturally be characterised by parameterised variants of classes based on branching programs in analogy to the classical counting classes. Finally, we underline the significance of this topic by providing a promising outlook showing several open problems and options for further directions of research.

In the uniform circuit model of computation, the width of a boolean circuit exactly characterises the ``space'' complexity of the computed function. Looking for a similar relationship in Valiant's algebraic model of computation, we propose width of an arithmetic circuit as a possible measure of space. We introduce the class VL as an algebraic variant of deterministic log-space L. In the uniform setting, we show that our definition coincides with that of VPSPACE at polynomial width. Further, to define algebraic variants of non-deterministic space-bounded classes, we introduce the notion of ``read-once'' certificates for arithmetic circuits. We show that polynomial-size algebraic branching programs can be expressed as a read-once exponential sum over polynomials in VL, ie $mbox{VBP}inSigma^R cdotmbox{VL}$. We also show that $Sigma^R cdot mbox{VBP} =mbox{VBP}$, ie VBPs are stable under read-once exponential sums. Further, we show that read-once exponential sums over a restricted class of constant-width arithmetic circuits are within VQP, and this is the largest known such subclass of poly-log-width circuits with this property. We also study the power of skew formulas and show that exponential sums of a skew formula cannot represent the determinant polynomial.